\documentclass[envcountsame]{llncs}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xspace}
\usepackage{tikz}
\usetikzlibrary{backgrounds,positioning,fit,patterns,shadows,calc}

\bibliographystyle{splncs03}

\newcommand*\samethanks[1][\value{footnote}]{\footnotemark[#1]}
\renewcommand{\paragraph}[1]{\smallskip\noindent{\bf #1.}\xspace}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver: Reduce margine
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\usepackage[left=1in,top=1in,right=1in,bottom=1in]{geometry} % Does NOT work right now
%\usepackage{fullpage}
%\usepackage{times}
\usepackage{booktabs}
\usepackage{threeparttable}
%\usepackage[small,compact]{titlesec}

%\setlength{\textheight}{9.2in}
%\setlength{\textwidth}{6.55in}


%http://tex.stackexchange.com/questions/4891/how-do-i-control-the-spacing-above-a-new-paragraph

\makeatletter
\renewcommand{\paragraph}{%
  \@startsection{paragraph}{4}%
  {\z@}{1ex \@plus 1ex \@minus .2ex}{-1em}%
  {\normalfont\normalsize\bfseries}%
}
\makeatother

%**************************************************
%**************************************************
%**************************************************


%--------------------------------------------------------------
%--------------------------------------------------------------
% Packages
%--------------------------------------------------------------
%--------------------------------------------------------------

\usepackage{tikz}
\usetikzlibrary{backgrounds,positioning,fit,patterns,shadows,calc}

\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amsmath}



\usepackage{calligra}
\usepackage[T1]{fontenc}

% ---------------------------------------------------------------------------------------
% ----- from http://mirrors.ibiblio.org/CTAN/macros/latex/exptl/thmtools/thmtools.pdf
%\usepackage{amsthm}
\usepackage{thmtools}


\usepackage{paralist}

%\usepackage{
%nameref,%\nameref
%hyperref,%\autoref
%% n.b. \Autoref is defined by thmtools
%cleveref,% \cref
%% n.b. cleveref after! hyperref
%}

\usepackage{nameref}
% Nicer hyperref obtained from Babis
%\definecolor{ForestGreen}{rgb}{0.1333,0.5451,0.1333}
%\definecolor{DarkRed}{rgb}{0.8,0,0}
%\definecolor{Red}{rgb}{1,0,0}
%\usepackage[linktocpage=true,
%	pagebackref=true,colorlinks,
%	linkcolor=DarkRed,citecolor=ForestGreen,
%	bookmarks,bookmarksopen,bookmarksnumbered]
%	{hyperref}
%Older style
\usepackage[linktocpage=true]{hyperref}
\usepackage{cleveref}

\usepackage{thm-restate} % See section 1.4 of the pdf above

% ---------------------------------------------------------------------------------------


\usepackage{xspace}
%\usepackage{theorem}
%\usepackage{graphicx}
%\usepackage{graphics}
%\usepackage{colordvi}
\usepackage{color}
%\usepackage{psfrag}
%\usepackage{eepic}
%\usepackage{subfigure}
%\usepackage[section]{algorithm}
%\usepackage{algorithmicx}
%\usepackage{algpseudocode}
%\usepackage[noend]{algpseudocode}
%\usepackage{wrapfig}
%\usepackage{lipsum}
\usepackage{enumitem}
\usepackage{comment}
%\usepackage{caption3} %reduce the size of captions under tables and figures. `caption3' works for sigalternate
\usepackage{caption}
\usepackage{subcaption}
\usepackage[noend]{algorithmic}
\usepackage[section,boxed]{algorithm}
\usepackage{algorithmicext}


%---------------------------------
% Definitions
%---------------------------------

\def\cP{\mathcal{P}}
\def\cH{\mathcal{H}}
\def\cA{\mathcal{A}}
\def\cT{\mathcal{T}}
\def\cD{\mathcal{D}}
\def\cC{\mathcal{C}}
\def\cG{\mathcal{G}}
\def\cJ{\mathcal{J}}
\def\cF{\mathcal{F}}
\def\cX{\mathcal{X}}
\def\cY{\mathcal{Y}}

\newcommand{\eps}{\varepsilon}
\renewcommand{\varepsilon}{\epsilon}
\newcommand{\st}{{\sf ST}\xspace}
\newcommand{\mcds}{{\sf MCDS}\xspace}
\newcommand{\scs}{{\sf SCS}\xspace}
\newcommand{\mis}{{\sf MIS}\xspace}
\newcommand{\mds}{{\sf MDS}\xspace}
\newcommand{\mhs}{{\sf MHS}\xspace}
\newcommand{\rmds}{{\sf RMDS}\xspace}
\newcommand{\mcsc}{{\sf MCSC}\xspace}
\newcommand{\bmds}{{\sf BMDS}\xspace}

\newcommand{\dimension}{\textsc{dim}}

\newconstruct{\PROC}{\textbf{procedure}}{}{\ENDPROC}{\textbf{end on}}

%\def\polylog{{\mathop{\mathrm{polylog}}\nolimits}}

\def\polylog{\operatorname{polylog}}

\newboolean{short}
\setboolean{short}{true}

\newcommand{\shortOnly}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\onlyShort}[1]{\ifthenelse{\boolean{short}}{#1}{}}
\newcommand{\longOnly}[1]{\ifthenelse{\boolean{short}}{}{#1}}
\newcommand{\onlyLong}[1]{\ifthenelse{\boolean{short}}{}{#1}}




%--------------------------------------------------------------
%--------------------------------------------------------------
%Theorems and such
%--------------------------------------------------------------
%--------------------------------------------------------------

%---- The code below is needed to make many refname commands work ----
%---- See http://tex.stackexchange.com/questions/49937/a-problem-with-thmtools-and-cleveref ----

\makeatletter
\def\thmt@refnamewithcomma #1#2#3,#4,#5\@nil{%
  \@xa\def\csname\thmt@envname #1utorefname\endcsname{#3}%
  \ifcsname #2refname\endcsname
    \csname #2refname\expandafter\endcsname\expandafter{\thmt@envname}{#3}{#4}%
  \fi
}
\makeatother

%\usepackage{thm-llncs}

%\declaretheorem[numberwithin=section,refname={Theorem,Theorems},Refname={Theorem,Theorems}]{theorem}
%\declaretheorem[numberwithin=section]{theorem}
%\declaretheorem[numberlike=theorem,refname={Lemma,Lemmas},Refname={Lemma,Lemmas}]{lemma}
%\declaretheorem[numberlike=theorem,refname={Corollary,Corollaries},Refname={Corollary,Corollaries}]{corollary}
%\declaretheorem[numberlike=theorem,name={Corollary},refname={Corollary,Corollaries},Refname={Corollary,Corollaries}]{corr}
%\declaretheorem[numberlike=theorem,refname={Proposition,Propositions},Refname={Proposition,Propositions}]{proposition}
%\declaretheorem[numberlike=theorem,refname={Observation,Observations},Refname={Observation,Observations}]{observation}
%\declaretheorem[numberlike=theorem,refname={Assumption,Assumptions},Refname={Assumption,Assumptions}]{assumption}
%\declaretheorem[numberlike=theorem,refname={Claim,Claims},Refname={Claim,Claims}]{claim}
%\declaretheorem[numberlike=theorem,refname={Definition,Definitions},Refname={Definition,Definitions}]{definition}
%\declaretheorem[style=remark,numberwithin=section,refname={Remarks,Remarks},Refname={Remarks,Remarks}]{remark}


%
%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{definition}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{observation}[theorem]{Observation}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{definition}[theorem]{Definition}
%
%
%%\newenvironment{exercise}{\underline{\bf Exercise}: }{}
%%%\newenvironment{proof}{\par \smallskip{\bf Proof:}}{\hfill\stopproof}
%%\def\stopproof{\square}
%%\def\square{\vbox{\hrule height.2pt\hbox{\vrule width.2pt height5pt \kern5pt
%%\vrule width.2pt} \hrule height.2pt}}
%%
%%%\newenvironment{definition}{\underline{\bf Definition}: }{}
%%%\newtheorem{definition}[theorem]{Definition}
%%\theoremstyle{definition}\newtheorem{definition}[theorem]{Definition}
%%%\newenvironment{definition}[1][Definition]{\begin{trivlist}
%%%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%


%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------
% Comments
%-------------------------------------------------------------------------------------
%-------------------------------------------------------------------------------------

%\addtolength{\voffset}{-0.15in}


%\def\ShowComment{True}

\ifdefined\ShowComment

\def\danupon#1{\marginpar{$\leftarrow$\fbox{D}}\footnote{$\Rightarrow$~{\sf #1 --Danupon}}}
\def\hsinhao#1{\marginpar{$\leftarrow$\fbox{H}}\footnote{$\Rightarrow$~{\sf #1 --Hsin-Hao}}}

\else

\def\danupon#1{}
\def\hsinhao#1{}

\fi



% This part changed {\em xxx} in the italic evironment (e.g. in theorem statements) to other fonts
% such as \sffamily,\bfseries, etc.
% See: http://tex.stackexchange.com/questions/6754/what-is-the-canonical-way-to-redefine-the-emph-command
% and http://www.forkosh.com/pstex/latexcommands.htm

%\makeatletter
%\DeclareRobustCommand{\em}{%
%  \@nomath\em \if b\expandafter\@car\f@series\@nil
%  \bfseries \else \itshape \fi}
%\makeatother




%--------------------------------------------------------------
%--------------------------------------------------------------
% Title page stuff
%--------------------------------------------------------------
%--------------------------------------------------------------

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Space saver for title page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\usepackage{titling}
%\setlength{\droptitle}{-55pt}



\title{Distributed Symmetry Breaking in Hypergraphs\thanks{The full version is available at \url{http://arxiv.org/abs/1405.1649}.}} 

\titlerunning{Distributed Symmetry Breaking in Hypergraphs}

\author{
Shay Kutten\inst{1}\fnmsep\thanks{Research supported in part by the Israel Science Foundation and by the Technion TASP center.}
\and 
Danupon Nanongkai\inst{2}\fnmsep\thanks{This work was partially done while at ICERM, Brown University USA and Nanyang Technological University, Singapore.}
\and
Gopal Pandurangan\inst{3}\fnmsep\thanks{This work was done while at Nanyang Technological University and Brown University. Research supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, Singapore MOE  AcRF Tier 1 grant MOE2012-T1-001-094, and a grant from the US-Israel Binational Science Foundation (BSF).}
\and
Peter~Robinson\inst{4}\thanks{Research supported by the grant Fault-tolerant Communication Complexity in Wireless Networks from the Singapore
MoE AcRF-2.}
}

\authorrunning{D. Nanongkai and H. Su}

\tocauthor{D. Nanongkai and H. Su}

\institute{Faculty of IE\&M, Technion, Haifa, Israel \and Faculty of Computer Science, University of Vienna, Austria \and Department of Computer Science, University of Houston, USA \and School of Computing, National University of Singapore}


\begin{document}

\maketitle

\input{abstract}



%\newpage
%\pagenumbering{arabic}
\tikzstyle{v}=[circle,draw=black,fill=white!30,thick,inner sep=2pt,minimum size=7mm,circular drop shadow]
\tikzstyle{b}=[v,double]


\input{intro}
\input{prelim}
\input{algorithms}
%\input{conclusion}
%\paragraph*{\bf Conclusion.}


\onlyShort{\vspace{-0.2in}}
\bibliography{papers}


\end{document}
